package class06;

/**
 *
 * 给定两个可能有环也可能无环的单链表,头结点head1和head2
 * 请实现一个函数,如果两个链表相交,请返回相交的第一个节点;如果不想交,返回null
 * 要求:如果两个链表长度之和为N,时间复杂度需达到O(N),额外空间复杂度需达到O(1)
 *
 * 处理单个链表环的思路: 单链表只有一个next指针, 如果成环, 那么一定是尾节点指向了链表中原本包含的地址
 * 1.利用set 或 map找到第一个重复地址
 * 那么使用一个 set 记录所有节点地址, 要么最终到达null(无环), 那么出现一个第二次出现的地址(在环上开始循环)
 *
 * 2.快慢指针
 * 慢指针先走一步,快指针先走两步, 然后慢指针步长为1,快指针步长为2
 * 如果快指针达到null(无环), 否则快慢指针第一次相遇
 * 相遇后,慢指针继续步长为1,快指针回到头节点,然后步长为1
 * 快慢指针第二次相遇的位置就是第一个相交的节点位置
 *
 * 处理两个无环链表是否相交思路:
 * 1.利用set, 先注册其中一条链表, 再遍历另外一条链表看其元素是否存在于set中
 * 2.先判断两个链表的end节点是否相等,如相等则存在相交节点,
 * 再在两个链表同长度的位置开始比较地址是否相等(谁长谁先走差值步, 相交部分等长)
 *
 * 不存在一个链表有环, 另一个链表无环, 但两链表相交(只有一个next指针会被破坏)
 *
 * 处理两个有环链表是否相交思路: (两个有环链表相交,那么两个链表一定是公用环)
 * 先求出两个链表入环的第一个节点(getLoopNode),loop1和loop2
 * loop1==loop2
 * 情况1:两个链表相交,且入环节点相同(把入环节点视为链表的end节点, 然后用两个链表均无环的方式求解)
 * loop1!=loop2
 * 从loop1出发,回到loop1时遇到过loop2
 * 情况2:两个链表相交,且入环节点不相同
 * 从loop1出发,回到loop1时未遇到过loop2
 * 情况3:两个有环链表不相交
 *
 *
 */
public class Code05_FindFirstIntersectNode {

	public static class Node {
		public int value;
		public Node next;

		public Node(int data) {
			this.value = data;
		}
	}

	public static Node getIntersectNode(Node head1, Node head2) {
		if (head1 == null || head2 == null) {
			return null;
		}
		Node loop1 = getLoopNode(head1);
		Node loop2 = getLoopNode(head2);
		if (loop1 == null && loop2 == null) {
			return noLoop(head1, head2);
		}
		if (loop1 != null && loop2 != null) {
			return bothLoop(head1, loop1, head2, loop2);
		}
		return null;
	}

	// 找到链表第一个入环节点，如果无环，返回null
	public static Node getLoopNode(Node head) {
		if (head == null || head.next == null || head.next.next == null) {
			return null;
		}
		// n1 慢  n2 快
		Node n1 = head.next; // n1 -> slow
		Node n2 = head.next.next; // n2 -> fast
		while (n1 != n2) {
			if (n2.next == null || n2.next.next == null) {
				return null;
			}
			//第一次相遇
			n2 = n2.next.next;
			n1 = n1.next;
		}
		n2 = head; // n2 -> walk again from head
		while (n1 != n2) {
			//第二次相遇
			n1 = n1.next;
			n2 = n2.next;
		}
		return n1;
	}

	// 如果两个链表都无环，返回第一个相交节点，如果不想交，返回null
	public static Node noLoop(Node head1, Node head2) {
		if (head1 == null || head2 == null) {
			return null;
		}
		Node cur1 = head1;
		Node cur2 = head2;
		int n = 0;
		while (cur1.next != null) {
			n++;
			cur1 = cur1.next;
		}
		while (cur2.next != null) {
			n--;
			cur2 = cur2.next;
		}
		if (cur1 != cur2) {
			return null;
		}
		// n  :  链表1长度减去链表2长度的值
		cur1 = n > 0 ? head1 : head2; // 谁长，谁的头变成cur1
		cur2 = cur1 == head1 ? head2 : head1; // 谁短，谁的头变成cur2
		n = Math.abs(n);
		while (n != 0) {
			n--;
			cur1 = cur1.next;
		}
		while (cur1 != cur2) {
			cur1 = cur1.next;
			cur2 = cur2.next;
		}
		return cur1;
	}

	// 两个有环链表，返回第一个相交节点，如果不想交返回null
	public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
		Node cur1 = null;
		Node cur2 = null;
		if (loop1 == loop2) {
			cur1 = head1;
			cur2 = head2;
			int n = 0;
			while (cur1 != loop1) {
				n++;
				cur1 = cur1.next;
			}
			while (cur2 != loop2) {
				n--;
				cur2 = cur2.next;
			}
			cur1 = n > 0 ? head1 : head2;
			cur2 = cur1 == head1 ? head2 : head1;
			n = Math.abs(n);
			while (n != 0) {
				n--;
				cur1 = cur1.next;
			}
			while (cur1 != cur2) {
				cur1 = cur1.next;
				cur2 = cur2.next;
			}
			return cur1;
		} else {
			cur1 = loop1.next;
			while (cur1 != loop1) {
				if (cur1 == loop2) {
					return loop1;
				}
				cur1 = cur1.next;
			}
			return null;
		}
	}

	public static void main(String[] args) {
		// 1->2->3->4->5->6->7->null
		Node head1 = new Node(1);
		head1.next = new Node(2);
		head1.next.next = new Node(3);
		head1.next.next.next = new Node(4);
		head1.next.next.next.next = new Node(5);
		head1.next.next.next.next.next = new Node(6);
		head1.next.next.next.next.next.next = new Node(7);

		// 0->9->8->6->7->null
		Node head2 = new Node(0);
		head2.next = new Node(9);
		head2.next.next = new Node(8);
		head2.next.next.next = head1.next.next.next.next.next; // 8->6
		System.out.println(getIntersectNode(head1, head2).value);

		// 1->2->3->4->5->6->7->4...
		head1 = new Node(1);
		head1.next = new Node(2);
		head1.next.next = new Node(3);
		head1.next.next.next = new Node(4);
		head1.next.next.next.next = new Node(5);
		head1.next.next.next.next.next = new Node(6);
		head1.next.next.next.next.next.next = new Node(7);
		head1.next.next.next.next.next.next = head1.next.next.next; // 7->4

		// 0->9->8->2...
		head2 = new Node(0);
		head2.next = new Node(9);
		head2.next.next = new Node(8);
		head2.next.next.next = head1.next; // 8->2
		System.out.println(getIntersectNode(head1, head2).value);

		// 0->9->8->6->4->5->6..
		head2 = new Node(0);
		head2.next = new Node(9);
		head2.next.next = new Node(8);
		head2.next.next.next = head1.next.next.next.next.next; // 8->6
		System.out.println(getIntersectNode(head1, head2).value);

	}

}
